import java.util.Stack;

/**
 * 笔试题方法的实现
 * **/

public class Method {

    //计数排序
    public static void countSort(int[] array) {
        //遍历数组找到最大值和最小值 - 找到才能确定数组的长度
        int maxVal = array[0];//假设最大值在0下标
        int minVal = array[0];//假设最小值在0下标
        for (int i = 0; i < array.length; i++) {
            if (array[i] > maxVal) {
                //此时i下标的值为最大值
                maxVal = array[i];
            }
            if (array[i] < minVal) {
                //此时i下标为最小值
                minVal = array[i];
            }
        }
        //确定数组的长度
        int len = maxVal - minVal + 1;
        int[] countArr = new int[len];
        //遍历数组统计每个数字出现的次数
        for (int i = 0; i < array.length; i++) {
            int val = array[i];
            countArr[val - minVal] ++;
        }
        int index = 0;
        //此时计数完毕 - 看每个下标的值是几就打印几
        for (int i = 0; i < countArr.length; i++) {
            while (countArr[i] > 0) {
                array[index] = i + minVal;
                index++;
                countArr[i]--;
            }
        }
    }
    //选择排序
    public static void selectSort(int[] array3) {
        for (int i = 0; i < array3.length; i++) {
            int minIndex = i;//假设最小值是当前的i下标的值
            for (int j = i + 1; j < array3.length; j++) {
                if (array3[j] < array3[minIndex]) {
                    //更新
                    minIndex = j;//将此时的j下标的值赋给minIndex
                }
            }
            if (i != minIndex) {
                //调用交换的方法交换i下标的值和minIndex的值
                swap(array3, minIndex, i);
            }
        }
    }

    //直接插入排序
    public static void insertSort(int[] array1) {
        //i下标从数组的第二个值开始
        for (int i = 1; i < array1.length ; i++) {
            int tmp = array1[i];//tmp存放i下标的值
            int j = i - 1;//j下标为i的前一个位置
            for (; j >= 0; j--) {
                if (array1[j] > tmp) {
                    //j下标的值大，将j下标的值放到j的下一个位置
                    array1[j + 1] = array1[j];
                }else {
                    //j下标的值较小，j小标的值要直接放到j的下一个位置
                    break;
                }
            }
            //此时j下标的值是负数了，将tmp的值放到j变量的后一个位置
            array1[j + 1] = tmp;
        }
    }
    //希尔排序
    public static void shellSort(int[] array2) {
        int gap = array2.length;//为数组的长度 - 为10
        while (gap > 1) {
            gap /= 2;//先是分成了5组，然后是2组，再是1组
            shell(array2, gap);//调用直接插入排序方法
        }
    }

    //实现直接插入排序方法
    public static void shell(int[] array2, int gap) {
        //i下标从第一组的第二个数据开始
        for (int i = gap; i < array2.length ; i++) {
            int tmp = array2[i];//tmp存放i下标的值
            int j = i - gap;//j下标为i-gap个位置
            //j每次-gap个位置
            for (; j >= 0; j-=gap) {
                if (array2[j] > tmp) {
                    //j下标的值大，将j下标的值放到j变量加上一个gap的位置上
                    array2[j + gap] = array2[j];
                }else {
                    //j下标的值较小，j下标的值要直接放到j变量加上一个gap的位置上
                    break;
                }
            }
            //此时j下标的值是负数了，将tmp的值放到j变量加上一个gap的位置上
            array2[j + gap] = tmp;
        }
    }

    //快速排序优化 挖坑法版,优化了查找基准的方法
    public static void quickSorts (int[] array) {
        quick(array, 0, array.length -1);
    }

    public static void quicks(int[] array, int start, int end) {
        //为了预防数据是 1 2 3 4 5 6  要么没有左树，要么没有右树
        if (start >= end) {
            return;
        }
        //接收基准
        int pivot = partitions(array, start, end);
        //递归掉方法
        quick(array, start, pivot - 1);
        quick(array, pivot + 1, end);
    }

    //挖坑法查找基准的方法
    public static int partitions(int[] array, int left, int right) {
        int pivot = array[left];//将坑位的数据   给pivot
        while (left < right) {
            //要是<=、>=，而不是<、>
            while (left < right && array[right] >= pivot) {
                //右边找比pivot小的
                right--;//--说明没找到
            }
            array[left] = array[right];
            while (left < right && array[left] <= pivot) {
                //左边找比pivot大的
                left++;//++说明没找到
            }
            array[right] = array[left];
        }
        //和原来的 left交换
        array[left] = pivot;
        return left;//返回的就是找到的基准
    }

    //判断括号字符串是不是合法的
    public static boolean chKParenthesis(String A, int num) {
        //创建一个栈
        Stack<Character> stack = new Stack<>();
        if (num % 2 != 0) {
            //长度为奇数，直接返回false
            return false;
        }
        //为偶数 - 遍历字符串
        for (char ch: A.toCharArray()) {
            //此时是左括号 - 压栈
            if (ch == '(' || ch == '{' || ch == '<' || ch == '[') {
                stack.push(ch);
            } else if (ch == ')' || ch == '}' || ch == '>' || ch == ']') { //当前为右括号
                //如果此时右括号下面没有左括号
                if (stack.isEmpty()) {
                    return false;
                } else if (stack.peek() == '(' || stack.peek() == '{' || stack.peek() == '<' || stack.peek() == '[') {
                    //弹出匹配的括号
                    stack.pop();
                }
            } else {
                //既不是既不是左括号也不是右括号
                return false;
            }
        }
        return stack.isEmpty();//判断当前栈是不是空的，返回true就位合法
    }

    //将字符串转为整数返回的方法
    public static int StrToInt(String str) {
        //将字符串放到数组中
        char[] chs = str.toCharArray();
        //如果字符串为空就直接返回0
        if (str.isEmpty()) {
            return 0;
        }
        //不为空 - 判断是正数还是负数
        /*
        * 为1就正数，为-1即使负数
        * */
        int symbol = 1;
        //此时是负数
        if (chs[0] == '-') {
            symbol = -1;//改为-1
            chs[0] = '0';
        } else if (chs[0] == '+') {
            //此时是正数
            symbol = 1;
            chs[0] = '0';
        }
        //遍历数组
        int sum = 0;
        for (int i = 0; i < chs.length; i++) {
            if (chs[i] < '0' || chs[i] > '9') {
                //不是数字
                sum = 0;
                break;
            }
            sum = sum * 10 + chs[i] - '0';
        }
        return symbol * sum;//是负数就会转为负数，正数就会转为正数
    }

    //得到两个数的最大值的方法
    public static int GetMax(int a, int b){
        return a > b ? a : b;
    }

    //判断是不是回文数的方法
    public static boolean isPalinDromes(String str) {
        //定义前后指针
        int left = 0;
        int right = str.length() - 1;
        while (left < right) {
            if (str.charAt(left) != str.charAt(right)) {
                //不是回文
                return false;
            }
            left++;
            right--;
        }
        return true;//是回文
    }

    //查找数组中出现次数超过一半的数字的方法 - 方法1
    public static int moreThanHalfNum(int[] array) {
        //调用归并排序的方法
        mergeSort(array);
        //quickSort(array);
        int len = array.length;//求数组长度
        int count = 0;//计数器
        //遍历数组
        for (int i = 0; i < array.length; i++) {
            if (array[i] == array[len / 2]) {
                count++;
            }
        }
        if (count > array[len / 2]) {
            return array[len / 2];//返回中间位置下标
        }
        return 0;
    }

    //查找数组中出现次数超过一半的数字的方法 - 方法2
    public static int moreThanHalfNums(int[] array) {
        int n = array.length;//求数组长度
        if (n == 0) {
            //长度为0
            return 0;
        }
        int soldier = array[0];//第一个下标的值是士兵
        int count = 1;//计数器
        //遍历数组
        for (int i = 0; i < n; i++) {
            if (array[i] == soldier) {
                //遇到相同的士兵
                count++;
            } else {
                //不同的士兵
                count--;
            }
            if (count == 0) {
                soldier = array[i];
                count = 1;
            }
        }
        //看此时soldier 是不是大于数组长度的一半
        count = 0;
        for (int i = 0; i < n; i++) {
            if (array[i] == soldier) {
                count++;
            }
        }
        if (count * 2 > n) {
            //此时soldier 就是大于数组长度一半的数字
            return soldier;
        }
        return 0;
    }

    //倒置的方法
    public static void reverse(char[] arr, int left, int right) {
        while (left < right) {
            //left小于right即为倒置结束
            char tmp = arr[left];
            arr[left] = arr[right];
            arr[right] = tmp;
            left++;//往右走
            right--;//往左走
        }
    }

    //归并排序的方法
    public static void mergeSort(int[] array) {
        //调用方法分解数组
        mergeSortChild(array, 0, array.length - 1);
    }

    //归排分解的方法
    public static void mergeSortChild(int[] array, int left, int right) {
        if (left == right) {
            return;
        }
        //求中间位置
        int mid = (left + right) / 2;
        mergeSortChild(array, left, mid);//递归分解左边
        mergeSortChild(array, mid + 1, right);//递归分解右边
        //开始合并
        mergre(array, left, mid, right);
    }

    //归排合并的方法
    public static void mergre(int[] array, int left, int mid, int right) {
        int s1 = left;
        int e1 = mid;
        int s2 = mid + 1;
        int e2 = right;
        //定义一个数组
        int[] tmpArr = new int[right - left + 1];
        int k = 0;
        while (s1 <= e1 && s2 <= e2) {
            if (array[s1] <= array[s2]) {
                tmpArr[k++] = array[s1++];
            } else {
                //这是s2小的情况
                tmpArr[k++] = array[s2++];
            }
        }
        //此时是s1或者s2超出区间范围了，但是有可能有一个还未超出范围
        while (s1 <= e1) {
            tmpArr[k++] = array[s1++];//都往后走
        }
        while (s2 <= e2) {
            tmpArr[k++] = array[s2++];
        }
        //此时数组中的数据是有序的了 - 此时要将排序好的数组传到原来的数组中
        for (int i = 0; i < k; i++) {
            array[i + left] = tmpArr[i];
        }
    }

    //快排的方法
    public static void quickSort(int[] array) {
        //调用方法分组
        quick(array, 0, array.length - 1);
    }

    //快排分组的方法
    public static void quick(int[] array, int start, int end) {
        //预防要么没有左树要么没有右树
        if (start >= end) {
            return;
        }
        //接受基准
        int ret = prtion(array, start, end);
        //递归实现
        quick(array, start, ret - 1);
        quick(array, ret + 1, end);
    }

    //快排找基准的方法
    public static int prtion(int[] array, int left, int right) {
        int i = left;
        int pivot = array[left];
        while (left < right) {
            //right往左边走找比pivot小的
            while (left < right && array[right] >= pivot) {
                right--;//没找到 - 往左走
            }
            //left往右走找比pivot大的
            while (left < right && array[left] <= pivot) {
                left++;
            }
            //交换左和右边的值
            swap(array, left, right);
        }
        //交换pivot和i的值
        swap(array, left, i);
        return left;
    }

    //交换的方法
    public static void swap(int[] array, int left, int right) {
        int tmp = array[left];
        array[left] = array[right];
        array[right] = tmp;
    }
}
